#! -*- encoding=utf-8 -*-

class Node:
    def __init__(self, key=0, value=0):
        self.key = key
        self.value = value
        self.prev = None
        self.next = None
    

    def __str__(self):
        val = '{%d: %d}' % (self.key, self.value)
        return val


class DoubleLinkedList():
    def __init__(self, capacity=0xffff):
        """
        param:  capacity: 链表容量
        param:  head: 头指针，指向头结点。 head.next == None。头结点的好处很多：
                1. 使首元结点（第一个正式存放数据的节点）无序进行特殊处理，表示都是 xxx.next
                2. 便于非空表和空表的统一处理。 判空为head.next == None。  不会存在头指针直接指向 None的情况
                3. 头结点还可存储一些信息。
        param:  tail: 尾指针，表为空时，头尾指针都指向头结点
        param:  cur_size: 当前链表长度
        """
        self.capacity = capacity
        self.head = Node()
        self.tail = self.head
        self.cur_size = 0


    def __add_head(self, node):
        """
            头插法向链表中插入数据，分三种情况:
            1. 为空链表
            2. 不为空, 没达到最大容量
            3. 达到最大容量
        """
        if not self.head.next:
            self.head.next = node
            node.prev = self.head
            self.tail = node
        elif self.cur_size < self.capacity:
            # 分析四个步骤，顺序还不能错。
            # node先将节点指向对应位置
            node.prev = self.head
            node.next = self.head.next
            # 在更新链表节点指针
            self.head.next.prev = node
            self.head.next = node
        else:
            pass

        self.cur_size += 1
        return node


    def __add_tail(self, node):
        """
            尾插法： 同样分三种情况
            设置头结点的好处就体现出来了！ 本来还要进行分情况讨论链表是否为空，
            这里就不需要讨论了~ ，都进行统一处理。
        """
        self.tail.next = node
        node.prev = self.tail
        self.tail = self.tail.next
        # 出bug了！ 这里的逻辑是当前插入的节点是新节点。 next = None。 但是如果是从一个链表中取出来该节点，放到另一个链表的尾部， 该节点的删除操作，netx指针还指向的有值，需要置None
        node.next = None
        
        self.cur_size +=1

        return node
    

    def __remove(self, node=None):
        """
            删除任意节点：
            1. 当不传入node时，默认尾部删除
            2. node就是 尾部结点
            3. 删除其他位置结点
        """
        if not node or node == self.tail:
            return self.__del_tail()    

        node.prev.next = node.next
        node.next.prev = node.prev
        self.cur_size -= 1
        
        return node


    def __del_head(self):
        """ 
            删除首元结点
            头结点使得处理逻辑都是一样的，直接调用 __remoove()方法 
        """
        return self.__remove(self.head.next)
    

    def __del_tail(self):
        """ 删除尾部结点 """    
        if self.head.next == None: # 空链表无法删除
            return 
        p = self.tail
        self.tail.prev.next = None
        self.tail = self.tail.prev
        self.cur_size -= 1
        return p


    # 提供对外的API接口
    def pop(self):
        """ 弹出头部节点 """
        return self.__del_head()


    def append(self, node):
        """ 默认尾部添加结点 """
        return self.__add_tail(node)


    def append_front(self, node):
        """ 往头部添加结点 """
        return self.__add_head(node)


    def remove(self, node = None):
        """ 删除节点 """
        return self.__remove(node)


    def print(self):
        """ 打印当前链表 """
        p = self.head
        line = ''
        while p.next:
            line += '%s' % p.next
            line += ' ==> ' 
            p = p.next

        print(line)



# 测试
if __name__ == '__main__':
    l = DoubleLinkedList(10)
    nodes = []
    for i in range(10):
        node = Node(i, i)
        nodes.append(node)

    l.append(nodes[0])
    l.print()
    l.append(nodes[1])
    l.print()
    l.pop()
    l.print()
    l.append(nodes[2])
    l.print()
    l.append_front(nodes[3])
    l.print()
    l.append(nodes[4])
    l.print()
    l.remove(nodes[2])
    l.print()
    l.remove()
    l.print()

